{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Possible Integer After at Most K Adjacent Swaps On Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #binary-indexed-tree #segment-tree #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #树状数组 #线段树 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minInteger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多 K 次交换相邻数位后得到的最小整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>num</code> 和一个整数&nbsp;<code>k</code> 。其中，<code>num</code> 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个 <strong>数位</strong> 。</p>\n",
    "\n",
    "<p>你可以交换这个整数相邻数位的数字 <strong>最多</strong>&nbsp;<code>k</code>&nbsp;次。</p>\n",
    "\n",
    "<p>请你返回你能得到的最小整数，并以字符串形式返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/17/q4_1.jpg\" style=\"height:40px; width:500px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = &quot;4321&quot;, k = 4\n",
    "<strong>输出：</strong>&quot;1342&quot;\n",
    "<strong>解释：</strong>4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = &quot;100&quot;, k = 1\n",
    "<strong>输出：</strong>&quot;010&quot;\n",
    "<strong>解释：</strong>输出可以包含前导 0 ，但输入保证不会有前导 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = &quot;36789&quot;, k = 1000\n",
    "<strong>输出：</strong>&quot;36789&quot;\n",
    "<strong>解释：</strong>不需要做任何交换。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = &quot;22&quot;, k = 22\n",
    "<strong>输出：</strong>&quot;22&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = &quot;9438957234785635408&quot;, k = 23\n",
    "<strong>输出：</strong>&quot;0345989723478563548&quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 30000</code></li>\n",
    "\t<li><code>num</code>&nbsp;只包含&nbsp;<strong>数字</strong>&nbsp;且不含有<strong>&nbsp;前导 0&nbsp;</strong>。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits](https://leetcode.cn/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits](https://leetcode.cn/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"4321\"\\n4', '\"100\"\\n1', '\"36789\"\\n1000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.q = [0] * (n + 1)\n",
    "\n",
    "    @staticmethod\n",
    "    def lowbit(x: int):\n",
    "        return x & -x\n",
    "\n",
    "    def update(self, x: int, d=1):\n",
    "        while x < len(self.q):\n",
    "            self.q[x] += d\n",
    "            x += BIT.lowbit(x)\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.q[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, s: str, k: int) -> str:\n",
    "        # make smallest first\n",
    "        mp = defaultdict(deque)\n",
    "        for i, c in enumerate(s):\n",
    "            mp[c].append(i)\n",
    "        res = []\n",
    "        bit = BIT(len(s))\n",
    "\n",
    "        while k and mp:\n",
    "            for c in sorted(mp):\n",
    "                v = mp[c]\n",
    "                if not v:\n",
    "                    del mp[c]\n",
    "                    continue\n",
    "                j = bit.query(v[0] + 1)\n",
    "                need = v[0] - j\n",
    "                if need <= k:\n",
    "                    bit.update(v.popleft() + 1)\n",
    "                    res.append(c)\n",
    "                    k -= need\n",
    "                    break\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            if mp[ch] and mp[ch][0] == i:\n",
    "                res.append(ch)\n",
    "                mp[ch].popleft()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.n = n\n",
    "        self.tree = [0]*(n+1)\n",
    "\n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "    \n",
    "    def update(self, x: int):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += 1\n",
    "            x += BIT.lowbit(x)\n",
    "    \n",
    "    def query(self, x: int) -> int:\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def queryRange(self, x: int, y: int) -> int:\n",
    "        return self.query(y) - self.query(x - 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        \"\"\"\n",
    "        在大小为k的窗口内找到最小数字 放置到第一位 然后把那个位置标记为None 代表被选走 如果k还有剩余找第二位 直到k为0 或者均交换完\n",
    "        但这样做会超时 因为每次找最小值太耗费时间了 因此采用如下方法\n",
    "        记录下0-9的位置 然后查找通过预处理的方式来做 比如上次找0到第四个 下一次就直接从第五个开始\n",
    "        但这样就不好计算置换的次数，通过记录已经用过元素并对换为求和来算\n",
    "        \"\"\"\n",
    "        n = len(num)\n",
    "        pos = [list() for _ in range(10)]#记录每个元素的下标\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            pos[ord(num[i]) - ord('0')].append(i + 1)\n",
    "        rs = \"\"\n",
    "        bit = BIT(n)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(10):\n",
    "                if pos[j]:#存在这样的数值\n",
    "                    behind = bit.queryRange(pos[j][-1] + 1, n)\n",
    "                    dist = pos[j][-1] + behind - i\n",
    "                    if dist <= k:\n",
    "                        bit.update(pos[j][-1])\n",
    "                        pos[j].pop()\n",
    "                        rs += str(j)\n",
    "                        k -= dist\n",
    "                        break\n",
    "        \n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.array = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, idx):\n",
    "        idx += 1 \n",
    "        while idx < len(self.array):\n",
    "            self.array[idx] += 1 \n",
    "            idx += idx & (- idx)\n",
    "    \n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        idx += 1 \n",
    "        while idx > 0:\n",
    "            res += self.array[idx]\n",
    "            idx -= idx & (- idx)\n",
    "        return res \n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        visit = [0] * n\n",
    "        dic = collections.defaultdict(lambda: collections.deque())\n",
    "        bit = BIT(n)\n",
    "        for i in range(n):\n",
    "            dic[int(num[i])].append(i)\n",
    "        res = ''\n",
    "        while True:\n",
    "            for v in range(10):\n",
    "                if not dic[v]:\n",
    "                    continue\n",
    "                idx = dic[v][0]\n",
    "                offset = idx - bit.query(idx - 1)\n",
    "                if offset <= k:\n",
    "                    dic[v].popleft()\n",
    "                    res += str(v)\n",
    "                    visit[idx] = 1 \n",
    "                    bit.update(idx)\n",
    "                    k -= offset\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        for i in range(n):\n",
    "            if not visit[i]:\n",
    "                res += num[i]\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "    \n",
    "    def update(self, x: int):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += 1\n",
    "            x += BIT.lowbit(x)\n",
    "    \n",
    "    def query(self, x: int) -> int:\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def queryRange(self, x: int, y: int) -> int:\n",
    "        return self.query(y) - self.query(x - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        pos = [list() for _ in range(10)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            pos[ord(num[i]) - ord('0')].append(i + 1)\n",
    "        \n",
    "        ans = \"\"\n",
    "        bit = BIT(n)\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(10):\n",
    "                if pos[j]:\n",
    "                    behind = bit.queryRange(pos[j][-1] + 1, n)\n",
    "                    dist = pos[j][-1] + behind - i\n",
    "                    if dist <= k:\n",
    "                        bit.update(pos[j][-1])\n",
    "                        pos[j].pop()\n",
    "                        ans += str(j)\n",
    "                        k -= dist\n",
    "                        break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                    \n",
    "            \n",
    "\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "    \n",
    "    def update(self, x: int):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += 1\n",
    "            x += BIT.lowbit(x)\n",
    "    \n",
    "    def query(self, x: int) -> int:\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def queryRange(self, x: int, y: int) -> int:\n",
    "        return self.query(y) - self.query(x - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        pos = [list() for _ in range(10)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            pos[ord(num[i]) - ord('0')].append(i + 1)\n",
    "        \n",
    "        ans = ''\n",
    "        bit = BIT(n)\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(10):\n",
    "                if pos[j]:\n",
    "                    behind = bit.queryRange(pos[j][-1] + 1, n)\n",
    "                    dist = pos[j][-1] + behind - i\n",
    "                    if dist <= k:\n",
    "                        bit.update(pos[j][-1])\n",
    "                        pos[j].pop()\n",
    "                        ans += str(j)\n",
    "                        k -= dist\n",
    "                        break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumArray:\n",
    "    def __init__(self, n:int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n+1)\n",
    "\n",
    "    def add(self, index: int, val: int):\n",
    "        while index <= self.n:\n",
    "            self.tree[index] += val\n",
    "            index += index & -index\n",
    "\n",
    "    def prefixSum(self, index) -> int:\n",
    "        s = 0\n",
    "        while index>0:\n",
    "            s += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return s\n",
    "\n",
    "    def update(self, index: int, val: int) -> None:\n",
    "        self.add(index + 1, val)\n",
    "\n",
    "    def sumRange(self, left: int, right: int) -> int:\n",
    "        return self.prefixSum(right + 1) - self.prefixSum(left)\n",
    "\n",
    "# 从最高位开始往后遍历（从左到右）\n",
    "# 对于每一位，从0到9，（从小到大）。去找后面每一个数字的最近位置\n",
    "# 因为交换会改变数字的位置，一个数字的实际位置，等于初始位置加上该数字后面发生交换的次数\n",
    "# 如果距离小于剩余的交换次数，那么可以交换。否则就继续往后找下一个更大的数字\n",
    "# 一定可以找到一个数字，因为如果剩余交换次数为0，那么当枚举到与当前位置相同的数字时，距离恰好为0\n",
    "# \n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        pos = [list() for _ in range(10)]\n",
    "        for i in range(n):\n",
    "            pos[ord(num[i])-ord('0')].append(i)\n",
    "        ans = \"\"\n",
    "        bit = NumArray(n)\n",
    "        for i in range(n):\n",
    "            for j in range(10):\n",
    "                if pos[j]:\n",
    "                    behind = bit.sumRange(pos[j][0]+1, n-1)\n",
    "                    dist = pos[j][0] + behind - i\n",
    "                    if dist<=k:\n",
    "                        bit.update(pos[j][0], 1)\n",
    "                        pos[j].pop(0)\n",
    "                        ans += str(j)\n",
    "                        k -= dist\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "    \n",
    "    def update(self, x: int):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += 1\n",
    "            x += BIT.lowbit(x)\n",
    "    \n",
    "    def query(self, x: int) -> int:\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def queryRange(self, x: int, y: int) -> int:\n",
    "        return self.query(y) - self.query(x - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        pos = [list() for _ in range(10)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            pos[ord(num[i]) - ord('0')].append(i + 1)\n",
    "        \n",
    "        ans = \"\"\n",
    "        bit = BIT(n)\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(10):\n",
    "                if pos[j]:\n",
    "                    behind = bit.queryRange(pos[j][-1] + 1, n)\n",
    "                    dist = pos[j][-1] + behind - i\n",
    "                    if dist <= k:\n",
    "                        bit.update(pos[j][-1])\n",
    "                        pos[j].pop()\n",
    "                        ans += str(j)\n",
    "                        k -= dist\n",
    "                        break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        res = []\n",
    "        while k > 0 and num:\n",
    "            for i in range(10):\n",
    "                ch = str(i)\n",
    "                idx = num.find(ch)\n",
    "                if idx < 0:\n",
    "                    continue\n",
    "                if idx <= k:\n",
    "                    res.append(ch)\n",
    "                    num = num[:idx] + num[idx + 1 :]\n",
    "                    k -= idx\n",
    "                    break\n",
    "        return \"\".join(res) + num\n",
    "\n",
    "\n",
    "# python 贪心+有序集合。\n",
    "# 首先要使首位尽可能小，从 0 到 9 遍历对应的位置列表，找到第一个距离小于等于 k 的位置 idx，即应该交换到首位。\n",
    "# 剩下的同理。显然每轮只需要 0 到 9 最近的位置，因此用 A 维护剩下的 0 到 9 分别对应的有序位置列表，每轮最多检查 10 个位置。\n",
    "# 难点在于候选位置 idx 和当前位置 i 的距离是变化的。当 idx 后有位置被交换时，idx 要后移一位。 因此需要求出 idx 后有多少个被交换的位置。\n",
    "# 可以用树状数组，也可以通过深入分析证明：idx 后被交换的位置数量=所有已交换位置中小于 num[idx] 的数量 - num[:idx] 中小于 num[idx] 的数量，从而 O(N) 求解。\n",
    "# 不过最简单粗暴的方法还是用 sortedcontainers.SortedList 维护所有已交换位置的有序集合，二分查找比 idx 大的数量即可。\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minInteger(self, num: str, k: int) -> str:\n",
    "#         if k <= 0 or not num:\n",
    "#             return num\n",
    "#         # 找到可以放在当前位置的最小数\n",
    "#         for i in range(10):\n",
    "#             idx = num.find(str(i))\n",
    "#             # 判断这个数字是否存在，以及是否可以通过交换放到当前位置\n",
    "#             if idx < 0:\n",
    "#                 continue\n",
    "#             if idx <= k:\n",
    "#                 # 将找到的数字放到最前面，并递归处理剩余的部分\n",
    "#                 return str(i) + self.minInteger(num[0:idx] + num[idx + 1 :], k - idx)\n",
    "#         # 如果所有数字都无法移动到当前位置，则返回原始数字\n",
    "#         return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        d = defaultdict(deque)\n",
    "        for i in range(len(num)):\n",
    "            d[num[i]].append(i)\n",
    "        \n",
    "        res = []\n",
    "        sl = SortedList() \n",
    "        \n",
    "        for j in range(len(num)):     # 每次处理第 j 位\n",
    "            for a in '0123456789':    # 贪心，每次试图先把小的元素移动到前面\n",
    "                if d[a]:\n",
    "                    i = d[a][0]       # 相同元素每次优先处理最左的\n",
    "                    dis = i + len(sl) - sl.bisect(i) - j   # 需要消耗的次数 = 当前的index + 当前右边已经移动到左边数量 - 当前处理的位数 j。\n",
    "                                                           # 其中 len(sl) - sl.bisect(i) 代表当前右边已经移动到左边数量，即当前 index 的增量\n",
    "                    if dis <= k:        # 如果需要消耗的次数不大于 k\n",
    "                        k -= dis        # k 减去消耗次数\n",
    "                        d[a].popleft()\n",
    "                        res.append(a)   # 每次不具体移动，只记录依次放置的数字\n",
    "                        sl.add(i)       # 平衡树\n",
    "                        break\n",
    "        \n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        res = []\n",
    "        while k > 0 and num:\n",
    "            for i in range(10):\n",
    "                ch = str(i)\n",
    "                idx = num.find(ch)\n",
    "                if idx < 0:\n",
    "                    continue\n",
    "                if idx <= k:\n",
    "                    res.append(ch)\n",
    "                    num = num[:idx] + num[idx + 1 :]\n",
    "                    k -= idx\n",
    "                    break\n",
    "        if num:\n",
    "            res.append(num)\n",
    "        return \"\".join(res)\n",
    "\n",
    "\n",
    "# python 贪心+有序集合。\n",
    "# 首先要使首位尽可能小，从 0 到 9 遍历对应的位置列表，找到第一个距离小于等于 k 的位置 idx，即应该交换到首位。\n",
    "# 剩下的同理。显然每轮只需要 0 到 9 最近的位置，因此用 A 维护剩下的 0 到 9 分别对应的有序位置列表，每轮最多检查 10 个位置。\n",
    "# 难点在于候选位置 idx 和当前位置 i 的距离是变化的。当 idx 后有位置被交换时，idx 要后移一位。 因此需要求出 idx 后有多少个被交换的位置。\n",
    "# 可以用树状数组，也可以通过深入分析证明：idx 后被交换的位置数量=所有已交换位置中小于 num[idx] 的数量 - num[:idx] 中小于 num[idx] 的数量，从而 O(N) 求解。\n",
    "# 不过最简单粗暴的方法还是用 sortedcontainers.SortedList 维护所有已交换位置的有序集合，二分查找比 idx 大的数量即可。\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minInteger(self, num: str, k: int) -> str:\n",
    "#         if k <= 0 or not num:\n",
    "#             return num\n",
    "#         # 找到可以放在当前位置的最小数\n",
    "#         for i in range(10):\n",
    "#             idx = num.find(str(i))\n",
    "#             # 判断这个数字是否存在，以及是否可以通过交换放到当前位置\n",
    "#             if idx < 0:\n",
    "#                 continue\n",
    "#             if idx <= k:\n",
    "#                 # 将找到的数字放到最前面，并递归处理剩余的部分\n",
    "#                 return str(i) + self.minInteger(num[0:idx] + num[idx + 1 :], k - idx)\n",
    "#         # 如果所有数字都无法移动到当前位置，则返回原始数字\n",
    "#         return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumArray:\n",
    "\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "        n = len(nums)\n",
    "        t = [0] * (n + 1)\n",
    "        for i, v in enumerate(nums, 1):  # 这部分是真的精彩，想出来的人真他妈是个天才\n",
    "            j = (i & -i) >> 1\n",
    "            while j:\n",
    "                v += t[i - j]\n",
    "                j >>= 1\n",
    "            t[i] = v\n",
    "        self.t = t\n",
    "\n",
    "    def update(self, index: int, val: int) -> None:\n",
    "        index += 1\n",
    "        delta = val - self.nums[index - 1]\n",
    "        self.nums[index - 1] = val\n",
    "        while index <= len(self.nums):\n",
    "            self.t[index] += delta\n",
    "            index += index & -index\n",
    "\n",
    "    def sumRange(self, right: int) -> int:\n",
    "        right += 1\n",
    "\n",
    "        def f(x):\n",
    "            ans = self.t[x]\n",
    "            while x:\n",
    "                x -= x & -x\n",
    "                if x:\n",
    "                    ans += self.t[x]\n",
    "                else:\n",
    "                    break\n",
    "            return ans\n",
    "\n",
    "        return f(right)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        num = deque(list(num))\n",
    "        d = defaultdict(deque)\n",
    "        for i, j in enumerate(num):\n",
    "            d[j].append(i)\n",
    "        ans = ''\n",
    "        numarr = NumArray([1] * n)\n",
    "        outer = 0\n",
    "        while outer < n:\n",
    "            if not k:\n",
    "                break\n",
    "            if num[outer] == '#':\n",
    "                outer += 1\n",
    "                continue\n",
    "            for i in range(int(num[outer])):\n",
    "                while d[str(i)] and (tmp := numarr.sumRange(d[str(i)][0]) - 1) <= k:\n",
    "                    k -= tmp\n",
    "                    ans += str(i)\n",
    "                    idx = d[str(i)][0]\n",
    "                    numarr.update(d[str(i)].popleft(), 0)\n",
    "                    num[idx] = '#'\n",
    "                if k == 0:\n",
    "                    break\n",
    "            ans += num[outer]\n",
    "            d[num[outer]].popleft()\n",
    "            num[outer] = '#'\n",
    "            numarr.update(outer, 0)\n",
    "            outer += 1\n",
    "            # while outer < n and num[outer] == '#':\n",
    "            #     outer += 1\n",
    "            # if outer < n:\n",
    "            #     ans += num[outer]\n",
    "            #     d[num[outer]].popleft()\n",
    "            #     num[outer] = '#'\n",
    "            #     numarr.update(outer, 0)\n",
    "            #     outer += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if num[i] != '#':\n",
    "                ans += num[i]\n",
    "        return ans       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeArrayRangeQuerySum:\n",
    "    # 模板：树状数组 单点增减 查询前缀和与区间和\n",
    "    def __init__(self, n: int) -> None:\n",
    "        # 索引从 1 到 n\n",
    "        self.t = [0] * (n + 1)\n",
    "        # 树状数组中每个位置保存的是其向前 low_bit 的区间和\n",
    "        return\n",
    "\n",
    "    def build(self, nums: List[int]) -> None:\n",
    "        # 索引从 1 开始使用数组初始化树状数组\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + nums[i]\n",
    "            self.t[i+1] = pre[i+1] - pre[i+1-self.lowest_bit(i+1)]\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def lowest_bit(i: int) -> int:\n",
    "        # 经典 low_bit 即最后一位二进制为 1 所表示的数\n",
    "        return i & (-i)\n",
    "\n",
    "    def query(self, i: int) -> int:\n",
    "        # 索引从 1 开始，查询 1 到 i 的前缀区间和\n",
    "        mi = 0\n",
    "        while i:\n",
    "            mi += self.t[i]\n",
    "            i -= self.lowest_bit(i)\n",
    "        return mi\n",
    "\n",
    "    def query_range(self, x: int, y: int) -> int:\n",
    "        # 索引从 1 开始，查询 x 到 y 的值\n",
    "        return self.query(y) - self.query(x-1)\n",
    "\n",
    "    def update(self, i: int, mi: int) -> None:\n",
    "        # 索引从 1 开始，索引 i 的值增加 mi 且 mi 可正可负\n",
    "        while i < len(self.t):\n",
    "            self.t[i] += mi\n",
    "            i += self.lowest_bit(i)\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        num = list(num)\n",
    "        dct = defaultdict(deque)\n",
    "        for i in range(n):\n",
    "            dct[num[i]].append(i)\n",
    "        tree = TreeArrayRangeQuerySum(n)\n",
    "        use = [0]*n\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if use[i]:\n",
    "                i += 1\n",
    "                continue\n",
    "            for d in range(int(num[i])):\n",
    "                w = str(d)\n",
    "                while dct[w] and use[dct[w][0]]:\n",
    "                    dct[w].popleft()\n",
    "                if dct[w]:\n",
    "                    cur = dct[w][0] - i - tree.query_range(i+1, dct[w][0]+1)\n",
    "                    if cur <= k:\n",
    "                        k -= cur\n",
    "                        ans.append(w)\n",
    "                        j = dct[w].popleft()\n",
    "                        use[j] = 1\n",
    "                        tree.update(j+1, 1)\n",
    "                        break\n",
    "            else:\n",
    "                use[i] = 1\n",
    "                ans.append(num[i])\n",
    "                i += 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        test = [deque() for _ in range(10)]\n",
    "        for i, n in enumerate(num):\n",
    "            test[int(n)].append(i)\n",
    "        res = []\n",
    "        b = []\n",
    "        for i in range(len(num)):\n",
    "            for j in range(10):\n",
    "                if test[j]:\n",
    "                    idx = test[j][0]\n",
    "                    x = bisect.bisect_left(b, idx)\n",
    "                    idx += len(b) - x\n",
    "                    cost = idx - i\n",
    "                    if cost <= k:\n",
    "                        k -= cost\n",
    "                        res.append(str(j))\n",
    "                        insort(b, test[j].popleft())\n",
    "                        break\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "        self.n = n\n",
    "\n",
    "    def update(self, x):\n",
    "\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "    \n",
    "    def get_sum(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x -= x & -x\n",
    "        return res\n",
    "\n",
    "    def query_range(self, x, y):\n",
    "        return self.get_sum(y) - self.get_sum(x - 1)\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "\n",
    "        pos = [[] for _ in range(10)]\n",
    "        n = len(num)\n",
    "        bit = Fenwick(n)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            pos[int(num[i])].append(i + 1)\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(10):\n",
    "                if pos[j]:\n",
    "                    cur = pos[j][-1]\n",
    "                    tmp = bit.query_range(cur + 1, n)\n",
    "                    if cur + tmp - i <= k:\n",
    "                        bit.update(cur)\n",
    "                        ans.append(str(j))\n",
    "                        k -= cur + tmp - i\n",
    "                        pos[j].pop()\n",
    "                        break\n",
    "\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def minInteger(self, s: str, k: int) -> str:\n",
    "        # make smallest first\n",
    "        mp = defaultdict(deque)\n",
    "        q = SortedDict()\n",
    "        for i, c in enumerate(s):\n",
    "            mp[c].append(i)\n",
    "            q[i] = c\n",
    "\n",
    "        res = []\n",
    "\n",
    "        while q and k:\n",
    "            for c in sorted(mp):\n",
    "                v = mp[c]\n",
    "                if not v:\n",
    "                    continue\n",
    "                j = q.bisect_left(v[0])\n",
    "                if j <= k:\n",
    "                    idx = v.popleft()\n",
    "                    q.pop(idx)\n",
    "                    res.append(c)\n",
    "                    k -= j\n",
    "                    break\n",
    "\n",
    "        res.extend(q.values())\n",
    "\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def minInteger(self, s: str, k: int) -> str:\n",
    "        # make smallest first\n",
    "        mp = defaultdict(deque)\n",
    "        q = SortedDict()\n",
    "        for i, c in enumerate(s):\n",
    "            mp[c].append(i)\n",
    "            q[i] = c\n",
    "\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            i, ch = q.items()[0]\n",
    "            for c in sorted(mp):\n",
    "                if c > ch:\n",
    "                    break\n",
    "                v = mp[c]\n",
    "                if not v:\n",
    "                    continue\n",
    "                j = q.bisect_left(v[0])\n",
    "                # print(q, v[0], j)\n",
    "                if j <= k:\n",
    "                    idx = v.popleft()\n",
    "                    q.pop(idx)\n",
    "                    res.append(c)\n",
    "                    k -= j\n",
    "                    break\n",
    "\n",
    "            # print(res, k)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT1:\n",
    "    \"\"\"单点修改,区间和查询\"\"\"\n",
    "    __slots__ = \"size\", \"bit\", \"tree\"\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self.tree = [0]*(n+1)\n",
    "    def add(self, index: int, delta: int) -> None:\n",
    "        # index 必须大于0\n",
    "        while index <= self.size:\n",
    "            self.tree[index]+=delta\n",
    "            index += index & -index\n",
    "    def _query(self, index: int) -> int: \n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "from sortedcontainers import SortedList        \n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n=len(num)\n",
    "        d=defaultdict(list)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            d[num[i]].append(i)\n",
    "        bit=[BIT1(n+10) for _ in range(10)]\n",
    "        sl=SortedList(list(range(n)))\n",
    "        for i,a in enumerate(num,1):\n",
    "            bit[int(a)].add(i,1)\n",
    "        res=\"\"\n",
    "        vis=[False]*n\n",
    "        while k>0 and len(sl)>0:\n",
    "            idx=sl[min(k,len(sl)-1)]\n",
    "            for i in range(10):\n",
    "                if bit[i].query(1,idx+1)>0:\n",
    "                    popidx=d[str(i)].pop()\n",
    "                    bit[i].add(popidx+1,-1)\n",
    "                    break\n",
    "            k-=sl.bisect_left(popidx)\n",
    "            res+=num[popidx]\n",
    "            sl.remove(popidx)\n",
    "            vis[popidx]=True\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                res+=num[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        n = len(num)\n",
    "        qs = [[] for _ in range(10)]\n",
    "        for i, x in enumerate(num):\n",
    "            qs[int(x)].append(i)\n",
    "        \n",
    "        root = SegmentTree().root\n",
    "        L = 0\n",
    "        R = 10 ** 9\n",
    "        s = \"\"\n",
    "        used = set()\n",
    "        while k > 0 and len(s) < n:\n",
    "            for q in qs:\n",
    "                if len(q) == 0: continue\n",
    "                t = SegmentTree.query(root, L, R, q[0]+1, n-1)\n",
    "                if q[0] + t - len(s) > k: continue\n",
    "                SegmentTree.update(root, L, R, q[0], q[0], 1)\n",
    "                k -= q[0] + t - len(s)\n",
    "                s += num[q[0]]\n",
    "                used.add(q[0])\n",
    "                heapq.heappop(q)\n",
    "                break\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in used:\n",
    "                s += num[i]\n",
    "        return s\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self) -> None:\n",
    "        self.ls = self.rs = None\n",
    "        self.val = self.add = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    @staticmethod\n",
    "    def update(node, lc, rc, l, r, v):\n",
    "        if l <= lc and rc <= r:\n",
    "            node.add += v\n",
    "            node.val += v\n",
    "            return\n",
    "        SegmentTree.pushdown(node)\n",
    "        mid = (lc + rc) // 2\n",
    "        if l <= mid:\n",
    "            SegmentTree.update(node.ls, lc, mid, l, r, v)\n",
    "        if r > mid:\n",
    "            SegmentTree.update(node.rs, mid + 1, rc, l, r, v)\n",
    "        node.val = node.ls.val + node.rs.val\n",
    " \n",
    "    @staticmethod\n",
    "    def query(node, lc, rc, l, r):\n",
    "        if l <= lc and rc <= r:\n",
    "            return node.val\n",
    "        SegmentTree.pushdown(node)\n",
    "        mid, ans = (lc + rc) // 2, 0\n",
    "        if l <= mid:\n",
    "            ans = SegmentTree.query(node.ls, lc, mid, l, r)\n",
    "        if r > mid:\n",
    "            ans += SegmentTree.query(node.rs, mid+1, rc, l, r)\n",
    "        return ans\n",
    "    \n",
    "    @staticmethod\n",
    "    def pushdown(node):\n",
    "        if node.ls is None: node.ls = Node()\n",
    "        if node.rs is None: node.rs = Node()\n",
    "        if not node.add: return\n",
    "        node.ls.add += node.add\n",
    "        node.rs.add += node.add\n",
    "        node.ls.val += node.add\n",
    "        node.rs.val += node.add\n",
    "        node.add = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        \n",
    "        def build(o,l,r):\n",
    "            if l == r:F[o] = [num[l],l,l];return\n",
    "            m = (l+r)>>1\n",
    "            build(2*o,l,m)\n",
    "            build(2*o+1,m+1,r)\n",
    "            F[o] = F[2*o].copy() if F[2*o][0] <= F[2*o+1][0] else F[2*o+1].copy()\n",
    "            return\n",
    "        \n",
    "        def delete(o,l,r,x):\n",
    "            if l == r:F[o][0] = '_';return\n",
    "            if lz[o]:\n",
    "                lz[2*o] += lz[o];lz[2*o+1] += lz[o]\n",
    "                F[2*o][1] += lz[o];F[2*o+1][1] += lz[o]\n",
    "                lz[o] = 0\n",
    "            m = (l+r)>>1\n",
    "            if m >= x:\n",
    "                delete(2*o,l,m,x)\n",
    "            else:\n",
    "                delete(2*o+1,m+1,r,x)\n",
    "            F[o] = F[2*o].copy() if F[2*o][0] <= F[2*o+1][0] else F[2*o+1].copy()\n",
    "            return\n",
    "\n",
    "        def update(o,l,r,a,b):\n",
    "            if l == r:F[o][1] += 1;return\n",
    "            if a <= l and r <= b:\n",
    "                lz[o] += 1;F[o][1] += 1;return\n",
    "            if lz[o]:\n",
    "                lz[2*o] += lz[o];lz[2*o+1] += lz[o]\n",
    "                F[2*o][1] += lz[o];F[2*o+1][1] += lz[o]\n",
    "                lz[o] = 0\n",
    "            m = (l+r) >> 1\n",
    "            if m >= a:\n",
    "                update(2*o,l,m,a,b)\n",
    "            if m < b:\n",
    "                update(2*o+1,m+1,r,a,b)\n",
    "            F[o] = F[2*o].copy() if F[2*o][0] <= F[2*o+1][0] else F[2*o+1].copy()\n",
    "            return\n",
    "        \n",
    "        def query(o,l,r,a,b):\n",
    "            if a <= l and r <= b:return F[o]\n",
    "            if lz[o]:\n",
    "                lz[2*o] += lz[o];lz[2*o+1] += lz[o]\n",
    "                F[2*o][1] += lz[o];F[2*o+1][1] += lz[o]\n",
    "                lz[o] = 0\n",
    "            m = (l+r)>>1\n",
    "            r1,r2 = ['_',-1,-1],['_',-1,-1]\n",
    "            if m >= a:\n",
    "                r1 = query(2*o,l,m,a,b)\n",
    "            if m < b:\n",
    "                r2 = query(2*o+1,m+1,r,a,b)\n",
    "            return r1 if r1[0] <= r2[0] else r2\n",
    "    \n",
    "        n = len(num)\n",
    "        l = list(num)\n",
    "        if k == 1:\n",
    "            for i in range(n-1):\n",
    "                if l[i] > l[i+1]:\n",
    "                    l[i+1],l[i] = l[i],l[i+1]\n",
    "                    return ''.join(l)\n",
    "        F = [['_',-1,-1] for i in range(4*n)]\n",
    "        lz = [0] * 4*n\n",
    "        pos = 0\n",
    "        pre = ''\n",
    "        build(1,0,n-1)\n",
    "        L = []\n",
    "        for i in range(n-1):\n",
    "            if k == 0:break\n",
    "            s,p1,prep1 = query(1,0,n-1,0,bisect_left(range(n-1),k,key = lambda x:x-bisect_right(L,x)))\n",
    "            L.insert(bisect_left(L,prep1),prep1)\n",
    "            if s == '_':break\n",
    "            pre += s\n",
    "            k -= (p1-pos)\n",
    "            l[prep1] = '_'\n",
    "            delete(1,0,n-1,prep1)\n",
    "            update(1,0,n-1,0,prep1)\n",
    "            pos += 1\n",
    "        rem = ''\n",
    "        for i in l:\n",
    "            if i == '_':continue\n",
    "            rem += i\n",
    "        return pre + rem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        if k <= 0 or not num:\n",
    "            return num\n",
    "\n",
    "        for i in range(0, 10):\n",
    "            index = num.find(str(i))\n",
    "            if index < 0:\n",
    "                continue\n",
    "            if index <= k:\n",
    "                if k == index:\n",
    "                    return str(i) + num[0:index] + num[index+1:]\n",
    "                return str(i) + self.minInteger(num[0:index] + num[index+1:], k - index)\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        if k <= 0 or not num:\n",
    "            return num\n",
    "        for i in range(10):\n",
    "            index = num.find(str(i))\n",
    "            if index < 0:\n",
    "                continue\n",
    "            if index <= k:\n",
    "                return str(i) + self.minInteger(\n",
    "                    num[0:index] + num[index + 1 :], k - index\n",
    "                )\n",
    "        return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minInteger(self, num: str, k: int) -> str:\n",
    "        if k <= 0 or not num:\n",
    "            return num\n",
    "\n",
    "        for i in range(0, 10):\n",
    "            index = num.find(str(i))\n",
    "            if index < 0:\n",
    "                continue\n",
    "            if index <= k:\n",
    "                if k == index:\n",
    "                    return str(i) + num[0:index] + num[index+1:]\n",
    "                return str(i) + self.minInteger(num[0:index] + num[index+1:], k - index)\n",
    "        return num\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
